package algorithm.sort;

import java.util.Arrays;

/**
 * 抄写java 传统归并排序
 * @author eii抄写java 传统归并排序
 * @sice 2020/11/27
 */
public class MergeSortDemo {

    private static final int INSERTIONSORT_THRESHOLD = 7;

    public static void main(String[] args) {
        Object[] a = {1, 6, 3, 8, 5, 9};
        Object[] aux = a.clone();
        mergeSort(a, aux, 0, a.length);
        System.out.println(Arrays.toString(aux));

        Object[] a2 = {1, 4, 56, 3, 28, 5, 9, 23, 43, 12, 54, 21, 15};
        Object[] aux2 = a2.clone();
        mergeSort(a2, aux2, 0, a2.length);
        System.out.println(Arrays.toString(aux2));
    }

    public static void mergeSort(Object[] src,
                                 Object[] dest,
                                 int low,
                                 int high) {
        int length = high - low;
        // Insertion sort on smallest arrays
        // 小数据集，使用插入排序
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i = 0; i < high; i++) {
                for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--) {
                    swap(dest, j - 1, j);
                }
            }
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;

        int mid = (low + high) >>> 1;
        mergeSort(dest, src, low, mid);
        mergeSort(dest, src, mid, high);

        // If list is already sorted, just copy from src to dest.  This is an optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = destLow, q = mid; i < destHigh; i++) {
            if( q >= destHigh || ((Comparable)src[p]).compareTo(src[q]) <= 0){
                dest[i] = src[p++];
            }else {
                dest[i] = src[q++];
            }
        }

    }

    /**
     * Swaps x[a] with x[b].
     */
    private static void swap(Object[] x, int a, int b) {
        Object t = x[a];
        x[a] = x[b];
        x[b] = t;
    }
}
